数据结构 - 2 散列表

发表于 | 分类于 | | 阅读次数:
字数统计: 1.5k | 阅读时长 ≈ 5

二叉树

为什么需要二叉树？

线性表查询快

链表（双向）插入删除快

哈希表结合两者优点，但是构建需要考虑的多

二叉树结合三者优点，且更符合人类认知+可以映射现实的结构

树

存储：

一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法

链式存储法：每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点

顺序存储法：完全二叉树适合，不浪费空间，堆其实就是一种完全二叉树。

高度、深度、层数：

“高度”这个概念，其实就是从下往上度量，3-0

“深度”这个概念在生活中是从上往下度量的，0-3

“层数”跟深度的计算类似，不过，计数起点是 1，也就是说根节点从1开始。

image-20190312155307376

二叉树

遍历

image-20190312154334354

前序遍历：打印顺序为本节点、左节点、右节点

中序遍历：打印顺序为左节点、本节点、右节点

后序遍历：打印顺序为左节点、右节点、本节点

时间复杂度是 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

// 真实代码
void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码，表示打印 root 节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码，表示打印 root 节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码，表示打印 root 节点
}

按层遍历：使用队列。

根节点入队列，此时队列不为空。取出队列第一个元素打印出来，若其左节点存在就存入队列，否组什么也不做，右节点同理。

直至队列为空，表示数的层次遍历结束，层次遍历也是一个广度优先遍历算法。

翻转二叉树

1
2
3
4
5
6
7
8
def inverttree(self, treenode):      #真正的翻转只有这8行代码
       if treenode == None:
           return None
       temp = treenode.lchild
       treenode.lchild = treenode.rchild
       treenode.rchild = temp
       self.inverttree(treenode.lchild)
       self.inverttree(treenode.rchild)

二叉查找树

支持：快速插入、删除、查找一个数据

要求：树中的任意一个节点，其左子树中的每个节点值都小于该节点，有字数节点值大于该节点。

查找、插入和删除

首先取根节点，两者相等则返回，数小于该节点则在其左子树中递归；大于则在右边递归查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// 节点类
class static class Node{
    private int data；
    private Node left;
    private Node right;
    // 初始化方法
    public Node(int data){
        this.data = data;
    }
}
// 二叉树类
public class binarySeachTree{
	// 声明一棵树，根节点为 tree
	private Node tree;
    
	// 1.查找函数
	public Node find(int data){
		//复制
		Node p = tree;
		// 不为空则继续查找
		while(data != null){
            // 是否相等
            if(data < p.data) p = p.left
            else if(data > p.data) p = p.right
            else return p；
		}
		// 为空返回空，表示没找到
		return null;
	}
    
    // 2.插入函数
    public void insert(int data){
        // 若根节点为空,根节点为该数据，实例化
        if (tree == null){
            tree = new Node(data)
                return;
        }
        Node p = tree;
        //  若不为空
        while(p != null){
            // 小于，查看节点左边是否有节点，没有就实例化，有就继续判断下一个
            if(data < p.data) {
                if(p.left = null){
                    p.left = new Node(data)
                }
              	p = p.left;
            }else if(data > p.data){
                if(p.right == null){
                    p.right = new Node(data)
                }
                 p = p.right;       
            }            
        }       
    }
    
    public class Question_39 {
    //----递归求二叉树深度----
    public static int treeDepth(BinaryTreeNode root){
        if(root == null){
            return 0;
        }
        int left = treeDepth(root.left);
        int right = treeDepth(root.right);
        
        return (left>right)?(left+1):(right+1);
    }
        
}

其他操作：最大最小、前驱后继节点

中序遍历（左中右）二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效率。

因此，二叉查找树也叫作二叉排序树。

支持重复数据的二叉查找树

方式一：一个节点不仅存储数据，通过链表和支持动态扩容的数组等数据结构，把值相同的数据存储于一个节点上。

方式二：更优雅。相等的时候看做大于该值。

二叉查找树的时间复杂度分析

最差情况：二叉查找树，根节点的左右子树极度不平衡，已经退化成链表。O(n)。

时间复杂度其实都跟树的高度成正比，也就是 O(height)。

两个极端情况的时间复杂度分别是 O(n) 和 O(logn)。

而对于完全二叉树：

问题就转变成另外一个了，也就是，如何求一棵包含 n 个节点的完全二叉树的高度？

完全二叉树的层数小于等于 log n +1，也就是说，完全二叉树的高度小于等于 （log n）。

平衡二叉树是 O(logn)。

散列表和二叉查找树比较

排序：散列表无序排序，输出有序数据前需要排序；二叉查找树有序，中序遍历可以在时间复杂度O(n)中，输出有序序列。

稳定性：散列表扩容耗时多、散列冲突的时候性能不稳定；平衡二叉查找树较稳定，时间稳定在 O(logn)。

构造复杂：散列表更加复杂，需要考虑散列函数、负载因子动态扩容、冲突解决。平衡二叉树只需要考虑平衡性。

空间：对于散列表的开放寻址法，装载因子不能太大，需要更多的空间。